/**
 * 单调队列
 * 
 * 求：大小为K的滑动窗口中最小值
 */

const K = 3; // 窗口大小
const Arr = [1, 3, -1, -3, 5, 3, 6, 7]
// -1 -3 -3 -3 3 3
// 3 3 5 5 6 7

function slidingWindow (k, arr){
  const N = arr.length;
  const minArr = []
  const maxArr = []
  // 单调递增队列，获取最小值。 
  // 维护下标
  let q = []; 
  for(let i = 0; i < N; i++){
    while(q.length && arr[q[q.length - 1]] > arr[i] ) q.pop();
    q.push(i);
    if(i - q[0] === k) q.shift(); // 队首元素超出区间范围
    if(i + 1 < k) continue; // 窗口中不足k个元素
    if(i + 1 >= k) minArr.push(arr[q[0]]);
  }

  q = [];
  for(let i = 0; i < N; i++){
    while(q.length && arr[q[q.length - 1]] < arr[i] ) q.pop();
    q.push(i);
    if(i - q[0] === k) q.shift();
    if(i + 1 < k) continue; // 窗口中部足k个元素
    if(i + 1 >= k) maxArr.push(arr[q[0]]);
  }
  return [minArr, maxArr]
}

const result = slidingWindow(K, Arr);
console.log(result);